package org.example.tree;

public class Node {

    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public void add(Node node){
        if (node == null){
            return;
        }
        //判断传入的值，和当前子树根节点的值关系
        if (node.value < this.value){
            if (this.left == null){
                this.left = node;
            }else{
                this.left.add(node);
            }
        }
        else{
            if (this.right == null){
                this.right = node;
            }
            else{
                this.right.add(node);
            }
        }
        //当完成添加一个节点后，如果：（右子树的高度 - 左子树的高度）> 1,左旋转
        if(rightHeight() - leftHeight() > 1){
            //如果它的右子树符合右旋转，则先对右子树进行右旋转，在对当前节点为根节点进行左旋转
            if (right.leftHeight() - right.rightHeight() > 1){
                right.rightRotate();
                leftRotate();
            }else{
                leftRotate();
            }
            return;
        }

        if (leftHeight() - rightHeight() > 1){
            //如果它的左子树符合左旋转条件
            if (left != null && left.rightHeight() > left.leftHeight()){
                //先对左子树进行左旋转
                left.leftRotate();
                //在对该节点为根节点进行右旋转
                rightRotate();
            }else{
                rightRotate();
            }

        }

    }

    //返回左子树的高度
    public int leftHeight(){
        if (left == null){
            return 0;
        }
        return left.height();
    }

    //返回右子树的高度
    public int rightHeight(){
        if (right == null){
            return 0;
        }
        return right.height();
    }

    //返回当前节点的高度，以该节点给根节点的树的高度
    public int height(){
        return Math.max(left == null ? 0:left.height(),
                right == null? 0 : right.height()) + 1;
    }

    //中序遍历
    public void infixOrder(){
        if (this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.infixOrder();
        }
    }

    //查找需要删除的节点
    public Node search(int value){

        if (value == this.value){
            return this;
        }else if (value < this.value){
            if (this.left == null){
                return null;
            }
            return this.left.search(value);
        }else{
            if (this.right == null){
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找需要删除节点的父节点
    public Node searchParent(int value){

        if (this.left != null && value == this.left.value ||
                this.right!= null && value == this.right.value){
            return this;
        }else if (this.left != null && value < this.value){
            return this.left.searchParent(value);
        }else if (this.right != null && value > this.value){
            return this.right.searchParent(value);
        }else{
            return null;
        }

    }

    //左旋转的方法
    public void leftRotate(){
         Node node = new Node(value);
         node.left = this.left;
         node.right = this.right.left;
         this.value = this.right.value;
         this.right = this.right.right;
         //把当前节点的左子节点设置成新的节点
         this.left = node;
    }

    //右旋转方法
    public void rightRotate(){
        Node node = new Node(value);
        node.right = this.right;
        node.left = this.left.right;
        this.value = this.left.value;
        this.left = this.left.left;
        this.right = node;
    }

}
